
#include <iostream>
using namespace std;

enum color
{
	RED,
	BLACK
};

template<class T>
struct RBTreeNode
{
	struct RBTreeNode<T>* _parent;
	struct RBTreeNode<T>* _left;
	struct RBTreeNode<T>* _right;

	T _Data;
	color _col;

	RBTreeNode(const T& Data)
		:_parent(nullptr)
		, _left(nullptr)
		, _right(nullptr)
		, _Data(Data)
		, _col(RED)
	{}
};

template<class T>
struct RBTreeIterator
{
	typedef struct RBTreeIterator<T> Self;
	typedef struct RBTreeNode<T> Node;

	Node* _pnode;
	RBTreeIterator(Node* pnode)
		:_pnode(pnode)
	{}

	T& operator*()
	{
		return _pnode->_Data;
	}

	T* operator&()
	{
		return &_pnode->_Data;
	}

	Self& operator++()
	{
		if (_pnode->_right)
		{
			Node* cur = _pnode->_right;
			while (cur->_left)
			{
				cur = cur->_left;
			}

			_pnode = cur;
		}
		else
		{
			if (_pnode->_parent)
			{
				Node* cur = _pnode;
				Node* parent = cur->_parent;
				while (parent && cur == parent->_right)
				{
					cur = parent;
					parent = parent->_parent;
				}

				if (parent && cur == parent->_left)
				{
					_pnode = cur;
				}
			}
			else
				_pnode = nullptr;
		}
		
		return *this;
	}
};

template<class K, class T,class KOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	typedef RBTreeIterator<T> iterator;

	iterator begin()
	{
		Node* cur = _root;
		while (cur && cur->_left)
		{
			cur = cur->_left;
		}

		return iterator(cur);
	}

	iterator end()
	{
		return iterator(nullptr);
	}

	bool Insert(const T& Data)                               
	{
		if (_root == nullptr)
		{
			_root = new Node(Data);
			_root->_col = BLACK;
			return true;
		}

		Node* cur = _root;
		Node* parent = nullptr;
		KOfT kot;

		while (cur)
		{
			if (kot(cur->_Data) < kot(Data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kot(cur->_Data) > kot(Data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}

		cur = new Node(Data);
		if (kot(cur->_Data) < kot(Data))
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;

		while (parent && parent->_col == RED)
		{
			Node* grandpa = parent->_parent;
			Node* uncle = nullptr;
			if (grandpa->_left == parent)
				uncle = grandpa->_right;
			else
				uncle = grandpa->_left;

			if (uncle && uncle->_col == RED)
			{
				parent->_col = BLACK;
				uncle->_col = BLACK;
				grandpa->_col = RED;
				cur = grandpa;
				parent = cur->_parent;
			}
			else
			{
				Node* grandpa = parent->_parent;
				if (parent == grandpa->_left && cur == parent->_left)
				{
					RotateL(grandpa);
					grandpa->_col = RED;
					parent->_col = BLACK;
				}
				else if (parent == grandpa->_right && cur == parent->_right)
				{
					RotateR(grandpa);
					grandpa->_col = RED;
					parent->_col = BLACK;
				}
				else if (parent == grandpa->_left && cur == parent->_right)
				{
					RotateL(parent);
					RotateR(grandpa);
					grandpa->_col = RED;
					cur->_col = BLACK;
				}
				else
				{
					RotateR(parent);
					RotateL(grandpa);
					grandpa->_col = RED;
					cur->_col = BLACK;
				}
				break;
			}
		}
		if (_root)
		_root->_col = BLACK;
	}

	void RotateL(Node* parent)
	{
		Node* cur = parent->_right;
		Node* LRChild = nullptr;
		if (cur)
			LRChild = cur->_right;

		Node* ancestor = parent->_parent;

		if (LRChild)
		{
			LRChild->_parent = parent;
		}
		if (cur)
			cur->_left = parent;

		parent->_parent = cur;
		parent->_right = LRChild;

		if (parent == _root)
		{
			_root = cur;
			if (cur)
				cur->_parent = nullptr;
		}
		else
		{
			if (ancestor->_left == parent)
			{
				ancestor->_left = cur;
			}
			else
			{
				ancestor->_right = cur;
			}
			if (cur)
				cur->_parent = ancestor;
		}
	}

	void RotateR(Node* parent)
	{
		Node* cur = parent->_left;
		Node* RLChild = cur->_left;
		Node* ancestor = parent->_parent;

		if (RLChild)
		{
			RLChild->_parent = parent;
		}
		parent->_parent = cur;
		parent->_left = RLChild;
		cur->_right = parent;

		if (parent == _root)
		{
			_root = cur;
		}
		else
		{
			if (parent == ancestor->_left)
			{
				ancestor->_left = cur;
			}
			else
			{
				ancestor->_right = cur;
			}
		}
		cur->_parent = ancestor;
	}

private:
	Node* _root = nullptr;
};
